Backward induction Totally Explained

Everything about Backward Induction totally explained

Backward induction is the process of reasoning backwards in time, from the end of a problem or situation, to determine an optimal course of action. It proceeds by first considering the last time a decision might be made and choosing what to do in any situation at that time. Using this information, one can then determine what to do at the second-to-last time of decision. This process continues backwards until one has determined the best action for every possible situation (for example for every possible information set) at every point in time. In the mathematical optimization method of dynamic programming, backward induction is one of the main methods for solving the Bellman equation. In game theory, backward induction is a method used to compute subgame perfect equilibria in sequential games. The only difference is that optimization involves just one decision maker, who chooses what do at each point of time, whereas game theory analyzes how the decisions of several players interact. That is, by anticipating what the last player will do in each situation, it's possible to determine what the second-to-last player will do, and so on.
In game theory, backward induction was first employed by John von Neumann and Oskar Morgenstern in their Theory of Games and Economic Behavior (1944). (External Link

)

An example of decision-making by backward induction

Consider an unemployed person who will be able to work for ten more years t = 1,2,...,10. Suppose that each year in which she remains unemployed, she may be offered a 'good' job that pays $100, or a 'bad' job that pays $44, with equal probability (50/50). Once she accepts a job, she'll remain in that job for the rest of the ten years. (Assume for simplicity that she cares only about her monetary earnings, and that she values earnings at different times equally, for example, the interest rate is zero.)
Should this person accept bad jobs? To answer this question, we can reason backwards from time t = 10.

At time 10, the value of accepting a good job is $100; the value of accepting a bad job is $44; the value of rejecting the job that's available is zero. Therefore, if she's still unemployed in the last period, she should accept whatever job she's offered at that time.
At time 9, the value of accepting a good job is $200 (because that job will last for two years); the value of accepting a bad job is 2*$44 = $88. The value of rejecting a job offer is $0 now, plus the value of waiting for the next job offer, which will either be $44 with 50% probability or $100 with 50% probability, for an average ('expected') value of 0.5*($100+$44) = $72. Therefore regardless of whether the job available at time 9 is good or bad, it's better to accept that offer than wait for a better one.
At time 8, the value of accepting a good job is $300 (it will last for three years); the value of accepting a bad job is 3*$44 = $132. The value of rejecting a job offer is $0 now, plus the value of waiting for a job offer at time 9. Since we've already concluded that offers at time 9 should be accepted, the expected value of waiting for a job offer at time 9 is 0.5*($200+$88) = $144. Therefore at time 8, it's more valuable to wait for a better offer than to accept a bad job.

It can be verified by continuing to work backwards that bad offers should only be accepted if one is still unemployed at times 9 or 10; they should be rejected at all times up to t = 8. The intuition is that if one expects to work in a job for a long time, this makes it more valuable to be picky about what job to accept.
A dynamic optimization problem of this kind is called an optimal stopping problem, because the issue at hand is when to stop waiting for a better offer. Search theory is the field of microeconomics that applies problems of this type to contexts like shopping, job search, and marriage.

An example of backward induction in game theory

Consider the ultimatum game, where one player proposes to split a dollar with another. The first player (the proposer) suggests a division of the dollar between the two players. The second player is then given the option to either accept the split or reject it. If the second player accepts, both get the amount suggested by the proposer. If rejected, neither receives anything.
Consider the actions of the second player given any arbitrary proposal by the first player (that gives the second player more than zero). Since the only choice the second player has at each of these points in the game is to choose between something and nothing, one can expect that the second will accept. Given that the second will accept all proposals offered by the first (that give the second anything at all), the first ought to propose giving the second as little as possible. This is the unique subgame perfect equilibrium of the Ultimatum Game. (It is important to note that the Ultimatum Game does have several other Nash equilibria.)
See also centipede game.

Backward induction and economic entry

Consider a dynamic game in which the players are an incumbent firm in an industry and a potential entrant to that industry. As it stands, the incumbent has a monopoly over the industry and doesn't want to lose some of its market share to the entrant. If the entrant chooses not to enter, the payoff to the incumbent is high (it maintains its monopoly) and the entrant neither loses nor gains (its payoff is zero). If the entrant enters, the incumbent can "fight" or "accommodate" the entrant. It will fight by lowering its price, running the entrant out of business (and incurring exit costs — a negative payoff) and damaging its own profits. If it accommodates the entrant it'll lose some of its sales, but a high price will be maintained and it'll receive greater profits than by lowering its price (but lower than monopoly profits).
Say that, the best response of the incumbent is to accommodate if the entrant enters. If the incumbent accommodates, the best response of the entrant is to enter (and gain profit). Hence the strategy profile in which the incumbent accommodates if the entrant enters and the entrant enters if the incumbent accommodates is a Nash equilibrium. However, if the incumbent is going to play fight, the best response of the entrant is to not enter. If the entrant doesn't enter, it doesn't matter what the incumbent chooses to do (since there's no other firm to do it to — note that if the entrant doesn't enter, fight and accommodate yield the same payoffs to both players; the incumbent won't lower its prices if the entrant doesn't enter). Hence fight is a best response of the incumbent if the entrant doesn't enter. Hence the strategy profile in which the incumbent fights if the entrant doesn't enter and the entrant doesn't enter if the incumbent fights is a Nash equilibrium. Since the game is dynamic, any claim by the incumbent that it'll fight is an incredible threat because by the time the decision node is reached where it can decide to fight (for example the entrant has entered), it would be irrational to do so. Therefore this Nash equilibrium can be eliminated by backward induction.

A paradox of backward induction

The unexpected hanging paradox is a paradox related to backward induction. Suppose a prisoner is told that she'll be executed sometime between Monday and Friday of next week. However, the exact day will be a surprise (for example she won't know the night before that she'll be executed the next day). The prisoner, interested in outsmarting her executioner, attempts to determine which day the execution will occur.
   She reasons that it can't occur on Friday, since if it hadn't occurred by the end of Thursday, she'd know the execution would be on Friday. Therefore she can eliminate Friday as a possibility. With Friday eliminated, she decides that it can't occur on Thursday, since if it hadn't occurred on Wednesday, she'd know that it had to be on Thursday. Therefore she can eliminate Thursday. This reasoning proceeds until she's eliminated all possibilities. She concludes that she won't be hanged next week.
   To her surprise, she's hanged on Wednesday.
   Here the prisoner reasons by backward induction, but seems to come to a false conclusion. Note, however, that the description of the problem assumes it's possible to surprise someone who is performing backward induction. The mathematical theory of backward induction doesn't make this assumption, so the paradox doesn't call into question the results of this theory. Nonetheless, this paradox has received some substantial discussion by philosophers.
Further Information

Get more info on 'Backward Induction'.

External Link Exchanges

Do you know how hard it is to get a link from a large encyclopaedia? Well we're different and will prove it. To get a link from us just add the following HTML to your site on a relevant page:

<a href="http://backward_induction.totallyexplained.com">Backward induction Totally Explained</a>

Then simply click through this link from your web page. Our crawlers will verify your link, extract the title of your web page and instantly add a link back to it. If you like you can remove the words Totally Explained and embed the link in article text.
As long as your link remains in place, we'll keep our link to you right here. Please play fair - our crawlers are watching. Your site must be closely related to this one's topic. Any kind of spamming, dubious practises or removing the link will result in your link from us being dropped and, potentially, your whole site being banned.